public class StringMatch {

    /**
     * 题目描述：
     * 给定主字符串s与模式字符串p，判断p是否是s的子串，如果是，则找出p在s中第一次出现时的下标。
     * 分析与解答：对于字符串的匹配，最直接的方法就是逐个比较字符串中的字符，这种方法比较容易实现，但是效率也比较低下。
     * 对于这种字符串匹配的问题，除了最常见的直接比较法外，经典的KMP算法（D.E.Knuth，J.H.Morris，V.R.Pratl操作）也是不二选择，它能能够显著提高运行效率，下面分别介绍这两种方法。
     *
     *
     * 方法二：KMP算法
     * 在方法一中，如果“P0 P1 P2…Pj-1” ==“Si-j…Si-1”，
     * 模式串的前j个字符已经和主串中i-j到i-1的字符进行了比较，此时如果Pj!=Si，
     * 那么模式串需要回退到0，主串需要回退到i-j+1的位置重新开始下一次比较。
     * 而在KMP算法中，如果Pj!=Si，那么不需要回退，即i保持不动，j也不用清0，
     * 而是向右滑动模式串，用Pk和Si继续匹配。这种方法的核心就是确定K的大小，
     * 显然，K的值越大越好。
     * 如果Pj!=Si，可以继续用Pk和Si 进行比较，
     * 那么必须满足：“P0 P1 P2…Pk-1” ==“Si-k…Si-1”在已经匹配的结果满足下面的关系：“Pj-k…Pj-1” ==“Si-k…Si-1”
     * 由以上这两个公式可以得出如下结论：“P0 P1 P2…Pk-1”=“Pj-k…Pj-1”
     * 因此，当模式串满足“P0 P1 P2…Pk-1”==“Pj-k…Pj-1”时，
     * 如果主串第i个字符与模式串第j个字符匹配失败，
     * 此时只需要接着比较主串第i个字符与模式串第k个字符。
     * 为了在任何字符匹配失败时都能找到对应K的值，这里给出next数组的定义，next[i]=m表示的意思为：“p0p1…pm-1”=“pi-m
     */


    /**
     * 方法功能：求字符串的next的数组
     *
     * @param p
     * @param next
     * @return
     */
    public static void getNext(String p, int[] next) {
        int i = 0, j = -1;
        next[0] = -1;
        while (i < p.length()) {
            if (j == -1 || p.charAt(i) == p.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else
                j = next[j];
        }
    }

    public static int match(String s, String p, int[] next) {
        if (s == null || p == null) {
            System.out.println("参数不合理");
            return -1;
        }
        int slen = s.length();
        int plen = p.length();
        //p肯定不是s的子串
        if (slen < plen) {
            return -1;
        }
        int i = 0, j = 0;
        while (i < slen && j < plen) {
            System.out.println("i=" + i + "," + "j=" + j);
            if (j == -1 || s.charAt(i) == s.charAt(j)) {
                //如果相同，则继续比较后面的字符
                i++;
                j++;
            } else {
                //主串i不需要回溯，从next数组中找出需要比较的模式中位置j
                j = next[j];
            }
        }
        if (j >= plen)//匹配成功
            return i - plen;
        return -1;
    }


    public static void main(String[] args) {
        String s = "abababaabcbab";
        String p = "abaabc";
        int len = p.length();
        int next[] = new int[len + 1];
        getNext(p, next);
        System.out.print("next数组：" + next[0]);
        for (int i = 1; i < len - 1; i++) {
            System.out.print("," + next[i]);
        }

        System.out.println();
        System.out.println("匹配结果：" + match(s, p, next));
    }
}
